public class 柱状图中最大的矩形 {
    public static int MAXN = 100001;
    public static int[] stack = new int[MAXN];
    public static int r;
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        r = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while (r > 0 && heights[i] <= heights[stack[r - 1]]) {
                int cur = stack[--r];
                int left = r > 0 ? stack[r - 1] : -1;
                ans = Math.max(ans,(i - left - 1) * heights[cur]);
            }
            stack[r++] = i;
        }
        while (r > 0) {
            int cur = stack[--r];
            int left = r > 0 ? stack[r - 1] : -1;
            ans = Math.max(ans,(n - left) * heights[cur]);
        }
        return ans;
    }
}
